package com.company.algo.listnode;

import com.company.algo.pojo.ListNode;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

/**
 * 判断一个链表是否为回文结构
 * 判断数组：
 * 双指针，一头一尾，若头不等于尾，则直接返回false
 * 遍历结束，没返回false，则返回true
 * 【判断链表】：
 * 1. 将链表元素装载进双向队列，通过双向队列pollFirst和pollLast来进行判决
 * 2.考虑链表的递归性质
 * currentNode 指针是先到尾节点，由于递归的特性再从后往前进行比较。
 * frontPointer 是递归函数外的指针。
 * 若 currentNode.val != frontPointer.val 则返回 false。
 * 反之，frontPointer 向前移动并返回 true。
 */
public class IsPail {

    public boolean isPalindrome(ListNode head) {
        Stack<ListNode> st = new Stack<>();
        ListNode left, right;
        left = right = head;
        while(right!=null){
            st.push(right);
            right = right.next;
        }
        boolean res = true;
        while(!st.isEmpty()){
            if(left.val == st.peek().val) break;
            if (left.val == st.pop().val){
                res =  true;
                left = left.next;
            }else return false;
        }
        return res;
    }

    public boolean isPail1(ListNode head) {
        Deque<Integer> deque = new LinkedList<>();
        while (head != null) {
            deque.addLast(head.val);
            head = head.next;
        }
        while (!deque.isEmpty()) {
            if (deque.size() <= 1) break;
            if (!deque.pollFirst().equals(deque.pollLast())) return false;
        }
        return true;
    }

    private ListNode frontPointer;      //递归函数之外的指针，指向头节点，每次递归返回true向后移动一位
    public boolean isPai(ListNode head) {
        frontPointer = head;
        return recurCheck(head);
    }
    //检查cur节点是否与fontPointer节点的值相同
    private boolean recurCheck(ListNode cur) {
        if (cur != null){
            if (!recurCheck(cur.next)) return false;
            if (cur.val != frontPointer.val) return false;
            frontPointer = frontPointer.next;
        }
        return true;
    }
}


